package com.leet.code.lcof;

import java.util.Arrays;

public class Code66 {

    public static void main(String[] args) {

        int[] a = {1, 2, 3, 4, 5};
        System.out.println(Arrays.toString(new Code66().constructArr(a)));
    }

    public int[] constructArr(int[] a) {
        int[] b = new int[a.length];
        b[0] = 1;

        for (int i = 1; i < b.length; i++) {
            b[i] = b[i - 1] * a[i - 1];
        }

        int j = 1;
        for (int i = a.length - 2; i >= 0; i--) {
            j = a[i + 1] * j;
            b[i] = b[i] * j;
        }
        return b;
    }

    public int[] constructArr1(int[] a) {
        int[] b = new int[a.length];
        j(a, b, 0, 1);
        return b;
    }

    public int j(int[] a, int[] b, int n, int j) {
        if (n == b.length) {
            return 1;
        }
        int hj = j(a, b, n + 1, j * a[n]);
        b[n] = j * hj;
        return a[n] * hj;
    }

}
